SP1026 FAVDICE - Favorite Dice

发布于 2020-09-12 | 分类于莫比乌斯反演 | 2分钟 | 302字数 | 浏览量：

令 $dp[i]$ 表示当前已经得到了 $i$ 个面后的期望次数。
有两种情况：

1.掷出已有的面，概率为 $\frac{i}{n}$

2.掷出新的面，概率为 $\frac{n-i}{n}$

那么有：

f[i]=\frac{i}{n}f[i]+\frac{n-i}{n}f[i+1]+1

\frac{n-i}{n}f[i]=\frac{n-i}{n}f[i+1]+1

f[i]=f[i+1]+\frac{n}{n-i}

边界条件 $f[n]=0$ , 倒推即可。

当然，把上式暴力展开后发现答案为 $n\sum_{i=1}^n\frac{1}{i}$

这其实是一个调和级数，由于精度要求不高 $n > 50$ 可用公式解决。

#include <cmath>
#include <cstdio>

const double Gamma = 0.577215664901532860606512090082402431042159335;
const int MAXN = 1000;
int t , n;
double Ans;

int main( ) {
	scanf("%d",&t);
	while( t -- ) {
		scanf("%d",&n);
        
        Ans = 0;
        if( n <= 50 )
		    for( int i = 1 ; i <= n ; i ++ ) Ans += 1.0 / i;
        else
            Ans = log( n ) + Gamma + 1.0 / 2 / n;
		printf("%.2f\n", Ans * n );
	}
	return 0;
}

SP1026 FAVDICE - Favorite Dice

感谢您的支持，我会继续努力的!